#ifndef _CFG_H_
#define _CFG_H_

#include "parser.h"
#include <map>
#include <set>
#include <stack>
#include <string>
#include <queue>
#include <stdlib.h>

enum X86REG {EAX = 1, EBX, ECX, EDX, EDI, ESI};

using namespace std;

class BasicBlock{
public:
	int in;//first line of the block, also can be seen as the id of the block
	int out;//last line of the block
	vector<int> preds;
	vector<int> succs;
	map<string, set<int> > definitions; //definitions that reach past this block from this block, maps variable name to line number.
	map<string, set<int> > predDefinitions; //incoming definitions from this block's predecessors that we might propagate
	map<string, set<int> > outDefinitions; //all definitions reaching out of this block;

	vector<set<string> > lives;
	vector<set<string> > defs;
	vector<set<string> > uses;

	//dominators
	set<int> dom;

	//dom tree
	int dt_parent;
	vector<int> dt_children;

	//dom frontier
	set<int> df;

	vector<Instr> phis;


	BasicBlock(int i, int o)
		:in(i), out(o), preds(), succs(), lives(), defs(), uses(), dom(), dt_parent(0), dt_children(), df(){
		set<string> s;
		lives.assign(out - in + 2, s);
		defs.assign(out - in + 1, s);
		uses.assign(out - in + 1, s);
	}

	set<string>& def(int idx){
		return defs[idx - in];
	}

	set<string>& use(int idx){
		return uses[idx - in];
	}

	set<string>& iLiveIn(int idx){
		return lives[idx - in];
	}

	set<string>& iLiveOut(int idx){
		return lives[idx - in + 1];
	}

	set<string>& bLiveIn(){
		return lives[0];
	}

	set<string>& bLiveOut(){
		return lives[out - in + 1];
	}

	void addPreds(int i);
	void addSuccs(int i);

	void resetLiveness();


};

class CFG{
public:
	vector<Instr>& is;
	map<int, BasicBlock *> nodes;//key: block id -- BasicBlock::in ; value: pointer to the block
	int entry;//entry of the function
	int end;//end of the function
	bool isMain;
	int nParamPushed;

	int dseInSCR;
	int dseOutSCR;
	vector<vector<int> > SCR; //Strongly connect regions for this function
	bool scr_found;
	int num_propagated;//number of constants propagated in this function
	int lines_moved;//number of lines moved with ssalicm;
	map<string, int> parameters;

	int numVars; //number of variables used in this CFG

	map<string, set<int> > var_def;
	map<string, set<string> > interference;
	map<string, int> spillCosts;
	map<string, int> coloring;
	map<string, int> var2reg;
	vector<string> spilled;

	CFG(vector<Instr>& instrs):is(instrs), nodes(), entry(0), end(0), isMain(false), SCR(1), scr_found(false), dseInSCR(0), dseOutSCR(0), num_propagated(0), lines_moved(0), nParamPushed(0){}
	~CFG(){
		map<int, BasicBlock *>::iterator it;
		for(it = nodes.begin(); it != nodes.end(); it++){
			delete (*it).second;
		}
	}

	void toAssembly(ostream& o, vector<string>& assembly){
		for( int i = entry; i <= end; i++){
			o << translateStatement(i, assembly);
		}
	}

	string x86reg(int r){
		string res("");
		switch(r){
			case EAX: res = "%eax"; break;
			case EBX: res = "%ebx"; break;
			case ECX: res = "%ecx"; break;
			case EDX: res = "%edx"; break;
			case EDI: res = "%edi"; break;
			case ESI: res = "%esi"; break;
		}
		return res;
	}

	string translateParam(Param& p){
		stringstream ss;
		string res;
		switch(p.type){
			case NA: res = "";break;
			case GP: res = "$gp";break;
			case FP: 
				if(p.value != 0){
					ss << "" << (p.value) << "(%ebp)"; res = ss.str(); break;
				}
				else{
					res = "%ebp"; break;
				}
			case CONST: ss << "$" << p.value; res = ss.str();break;
			case ADDR_OFFSET: ss <<"$"<< (p.value); res = ss.str();break;//divid by 2 here?
			case FIELD_OFFSET: ss <<"$"<< (p.value); res = ss.str();break;
			case LOCAL_VAR: res = x86reg(var2reg[p.literal]); 
				//if(res.compare("") == 0){
					//ss << "" << (p.value) << "(%ebp)"; 
				//	res = ss.str();
				//}
				break;//todo
			case REG: ss << "" << p.value; res = x86reg(var2reg[ss.str()]);break;//todo
			case LABEL: ss << ".label_" << p.value; res = ss.str();break;
		}
		return res;
	}

	string translateStatement(int idx, vector<string>& assembly){
		map<string, int >::iterator it;
		stringstream ss;
		ss<<""<<idx;
		string des;
		bool useDes = false;
		if(var2reg.find(ss.str()) != var2reg.end()){
			des = x86reg(var2reg[ss.str()]);
			useDes = true;
		}

		ss.str("");

		if(idx >= entry && idx <= end){
			Instr& instr = is[idx];
			Param & p1 = instr.param1;
			Param & p2 = instr.param2;
			
			if(instr.hasLabel){
				ss<<".label_"<<idx<<":\n";
				assembly.push_back(ss.str());
				ss.str("");
			}

			/*if(p1.type == LOCAL_VAR){
				ss<<"movl "<< (p1.value/2) << "(%ebp), "<< x86reg(var2reg[p1.literal]) << endl;
			}

			if(p2.type == LOCAL_VAR && instr.opt != MOVE){
				ss<<"movl "<< (p2.value/2) << "(%ebp), "<< x86reg(var2reg[p2.literal]) << endl;
			}*/

			string sp1, sp2;
			sp1 = translateParam(p1);
			sp2 = translateParam(p2);
			stringstream funcname;

			switch(instr.opt){
				case ADD:
					if(sp2.compare(des) == 0){
						ss << "\taddl " << sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(sp1.compare(des) == 0){
						ss << "\taddl " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tmovl "<< sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\taddl " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					break;
				case SUB:
					if(sp2.compare(des) == 0){
						ss << "\tpush " << sp1 << endl; 
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tsubl " << sp2 << ", " << sp1 << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tmovl " << sp1 << ", " << sp2 << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpop " << sp1 << endl; 
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(sp1.compare(des) == 0){
						ss << "\tsubl " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tmovl "<< sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tsubl " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					break;
				case MUL:
					if(sp2.compare(des) == 0){
						ss << "\timull " << sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(sp1.compare(des) == 0){
						ss << "\timull " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tmovl "<< sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\timull " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					break;
				case DIV:
					ss << "\tpushl %edx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpushl %eax" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					if(sp1.compare("%eax") != 0){
						ss << "\tmovl " << sp1 << ", %eax" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					ss << "\tmovl $0, %edx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					
					if(sp2[0] == '$'){
						ss << "\tpushl %ecx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tmovl " << sp2 << ", %ecx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tidivl " << "%ecx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %ecx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(sp2.compare("%eax") == 0){
						ss << "\tidivl " << "(%esp)" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(sp2.compare("%edx") == 0){
						ss << "\tidivl " << "4(%esp)" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tidivl " << sp2 << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}

					if(des.compare("%eax") == 0){
						ss << "\tpopl %edx" << endl;//cannot pop old eax back, pop old eax to edx instead
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %edx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(des.compare("%edx") == 0){
						ss << "\tmovl %eax, %edx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %eax" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\taddl $4, %esp" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tmovl %eax, " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %eax" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %edx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
									
					break;
				case MOD:
					ss << "\tpushl %edx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpushl %eax" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					if(sp1.compare("%eax") != 0){
						ss << "\tmovl " << sp1 << ", %eax" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					ss << "\tmovl $0, %edx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					
					if(sp2[0] == '$'){
						ss << "\tpushl %ecx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tmovl " << sp2 << ", %ecx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tidivl " << "%ecx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %ecx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(sp2.compare("%eax") == 0){
						ss << "\tidivl " << "(%esp)" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(sp2.compare("%edx") == 0){
						ss << "\tidivl " << "4(%esp)" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tidivl " << sp2 << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}

					if(des.compare("%edx") == 0){
						ss << "\tpopl %eax" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\taddl $4, %esp" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(des.compare("%eax") == 0){
						ss << "\tmovl %edx, %eax" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\taddl $4, %esp" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %edx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tmovl %edx, " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %eax" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %edx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					break;
				case NEG:
					if(sp1.compare(des) != 0){
						ss << "\tmovl " << sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					ss << "\tnegl " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
				case CMPEQ:
					//if(sp1.compare(des) != 0)
					//	ss << "\tmovl " << sp1 << ", " << des << endl;
					//ss << "\tsubl " << sp2 << ", " << des << endl;
					if(sp2.compare(des) == 0){
						ss << "\tpush " << sp1 << endl; 
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tsubl " << sp2 << ", " << sp1 << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tmovl " << sp1 << ", " << sp2 << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpop " << sp1 << endl; 
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(sp1.compare(des) == 0){
						ss << "\tsubl " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tmovl "<< sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tsubl " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					ss << "\tcmpl $0, " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tje " << ".cmpeq_" << idx << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tmovl $0, " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tjmp " << ".endcmpeq_" << idx << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << ".cmpeq_" << idx << ": " << endl << "\tmovl $1, " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << ".endcmpeq_" << idx << ": " << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
				case CMPLE:
					//if(sp1.compare(des) != 0)
					//	ss << "\tmovl " << sp1 << ", " << des << endl;
					//ss << "\tsubl " << sp2 << ", " << des << endl;
					if(sp2.compare(des) == 0){
						ss << "\tpush " << sp1 << endl; 
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tsubl " << sp2 << ", " << sp1 << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tmovl " << sp1 << ", " << sp2 << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpop " << sp1 << endl; 
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(sp1.compare(des) == 0){
						ss << "\tsubl " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tmovl "<< sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tsubl " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					ss << "\tcmpl $0, " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tjle " << ".cmple_" << idx << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tmovl $0, " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tjmp " << ".endcmple_" << idx << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << ".cmple_" << idx << ": " << endl << "\tmovl $1, " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << ".endcmple_" << idx << ": " << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
				case CMPLT:
					//if(sp1.compare(des) != 0)
					//	ss << "\tmovl " << sp1 << ", " << des << endl;
					//ss << "\tsubl " << sp2 << ", " << des << endl;
					if(sp2.compare(des) == 0){
						ss << "\tpush " << sp1 << endl; 
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tsubl " << sp2 << ", " << sp1 << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tmovl " << sp1 << ", " << sp2 << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpop " << sp1 << endl; 
						assembly.push_back(ss.str());
						ss.str("");
					}
					else if(sp1.compare(des) == 0){
						ss << "\tsubl " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tmovl "<< sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tsubl " << sp2 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					ss << "\tcmpl $0, " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tjl " << ".cmplt_" << idx << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tmovl $0, " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tjmp " << ".endcmplt_" << idx << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << ".cmplt_" << idx << ": " << endl << "\tmovl $1, " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << ".endcmplt_" << idx << ": " << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
				case BR:
					ss << "\tjmp " << sp1 << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
				case BLBC:
					ss << "\tcmpl $0, " << sp1 << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tje " << sp2 << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
				case BLBS:
					ss << "\tcmpl $1, " << sp1 << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tje " << sp2 << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
				case CALL:
					ss << "\tcall function_" << p1.value << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\taddl $" << (nParamPushed * 4) << ", %esp" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					nParamPushed = 0;
					break;
				case LOAD:
					if(p1.type != FP){
						ss << "\tmovl (" << sp1 << "), " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tmovl " << sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					break;
				case STORE:
					if(p2.type != FP){
						ss << "\tmovl " << sp1 << ", (" << sp2 << ")" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					else{
						ss << "\tmovl " << sp1 << ", " << sp2 << "" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					break;
				case MOVE:
					if(sp1.compare(sp2) != 0){
						ss << "\tmovl " << sp1 << ", " << sp2 << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					if(sp2.compare(des) != 0){
						if(useDes){
							if(sp1.compare(des) != 0){
								ss << "\tmovl " << sp1 << ", " << des << endl;
						assembly.push_back(ss.str());
						ss.str("");
							}
						}
					}
					break;
				case READ:
					ss << "\tsubl $4, %esp" << endl; //reserve space for the read-in value
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpushl %edx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpushl %eax" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpushl %ecx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tmovl $.LC0, %edx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tmovl stdin, %eax" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tleal 12(%esp), %ecx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpushl %ecx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpushl %edx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpushl %eax" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tcall __isoc99_fscanf" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\taddl $12, %esp" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpopl %ecx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpopl %eax" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpopl %edx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpopl " << des << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
				case WRITE:
					ss << "\tpushl %ecx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpushl " << sp1 << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tmovl $.LC0, %ecx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpushl %ecx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tcall printf" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\taddl $8, %esp" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpopl %ecx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
				case WRL:
					ss << "\tpushl %ecx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tsubl $4, %esp" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tmovl $10, (%esp)" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tcall putchar" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\taddl $4, %esp" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tpopl %ecx" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
				case PARAM:
					ss << "\tpushl " << sp1 << endl;
					assembly.push_back(ss.str());
					ss.str("");
					nParamPushed++;
					break;
				case ENTER:
					if(isMain)
						funcname << "main" ;
					else
						funcname << "function_" << entry ;

					ss << ".globl " << funcname.str() << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << ".type " << funcname.str() << ", @function" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << funcname.str() << ": " << endl;
					assembly.push_back(ss.str());
					ss.str("");

					ss << "\tpushl %ebp" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					ss << "\tmovl %esp, %ebp" <<endl;
					assembly.push_back(ss.str());
					ss.str("");
					if(!isMain){
						ss << "\tpushl %eax" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpushl %ebx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpushl %ecx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpushl %edx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpushl %edi" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpushl %esi" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}
					ss << "\tsubl $" << (p1.value) << ", %esp" <<endl;
					assembly.push_back(ss.str());
					ss.str("");

					for(it = parameters.begin(); it != parameters.end(); it++){
						string name = (*it).first;
						int offset = (*it).second;
						if(var2reg.find(name) != var2reg.end()){
							ss << "\tmovl " << (offset/2) << "(%ebp), " << x86reg(var2reg[name]) << endl;
							assembly.push_back(ss.str());
							ss.str("");
						}
					}

					break;
				case RET:
					ss << "\taddl $" << (is[entry].param1.value) << ", %esp" << endl;
					assembly.push_back(ss.str());
					ss.str("");

					if(!isMain){
						ss << "\tpopl %esi" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %edi" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %edx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %ecx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %ebx" << endl;
						assembly.push_back(ss.str());
						ss.str("");
						ss << "\tpopl %eax" << endl;
						assembly.push_back(ss.str());
						ss.str("");
					}

					ss << "\tpopl %ebp" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					
					ss << "\tret" << endl;
					assembly.push_back(ss.str());
					ss.str("");
					break;
			}
		}
		return ss.str();
	}

	bool build(int start);
	void output(ostream& o);

	void findSCR();
	void printSCR(ostream& o);

	void scp();
	void printSCP(ostream& o);
	
	void liveness();
	bool dse();
	void printLiveness(ostream& o);
	void resetLiveness();

	void findDominators();
	void buildDomTree();
	void findDomFrontier(BasicBlock *);
	void printDomFrontier(ostream& o);

	void placePhi();
	void printVarDef(ostream& o);
	void printPhi(ostream& o);

	void rename();

	void ssacp(); //Single Static Assignment Constant Propagation
	bool ssalicm(int scr); //Single Static Assignment Loop Invarient Code Motion
	void printssalicm(ostream& o);

	void makeInterferenceGraph();
	void printInterferenceGraph(ostream& o);
	bool colorInterferenceGraph();
	void printColoring(ostream& o);
	void findSpillCosts();

private:

	void findSCRhelper(set<int>& assigned, map<int, int>& ordering, int current, int& c, stack<int>& S, stack<int>& P, int& cur_scr);
	void findDefinitions();
	void reachingDefinitions(queue<BasicBlock*>& workList, set<int>& doneList);
	void propagate(int line, Instr* inst, map<string, set<int> >& curDefinitions, int& propagated, bool& changed);

	void initDefUse();
	bool isInSCR(int idx);

	void initVarDef();
	void renameHelper(BasicBlock * b, map<string, int>& c, map<string, stack<int> >& s);

	//ssalicm helpers
	bool canMove(int line, int scr);
	void doMove(const vector<int>& linestomove, int scr);
	bool inSCR(int line, int scr);
	bool definedInSCR(const Param& p, int scr);

};





#endif
